package dfs_bfs.test37;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/9 11:27
 */
public class Solution2 {

    // dfs， 吊炸天

    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][][] cells = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
        // 首先将布尔标志数组更新
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int t = c - '1';
                    rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;
                }
            }
        }
        dfs(board, 0, 0);
    }

    private boolean dfs(char[][] board, int r, int c) {
        if (c == 9) {
            r++;
            c = 0;
        }
        if (r == 9) return true;
        if (board[r][c] != '.') return dfs(board, r, c + 1);
        for (int i = 0; i < 9; i++) {
            if (!rows[r][i] && !cols[c][i] && !cells[r / 3][c / 3][i]) {
                rows[r][i] = cols[c][i] = cells[r / 3][c / 3][i] = true;
                board[r][c] = (char) ('1' + i);
                if (dfs(board, r, c + 1)) return true;
                board[r][c] = '.';
                rows[r][i] = cols[c][i] = cells[r / 3][c / 3][i] = false;
            }
        }
        return false;
    }

}
